//基数排序
/*
最大值
根据最大值获取个十百千位
根据获取的个十百千位进行排序
*/

//基数排序 平均时间复杂度O(N+K),空间复杂度O(N+K),稳定
int maxBit(vector<int> vec) { //返回vector中最长的元素有几位
    int max = vec[0];
    for (int i = 1; i < vec.size(); i++) {
        if (vec[i] > max) max = vec[i];
    }
    int p = 1;
    while (max/10 != 0) {
        max = max / 10;      
        p++;
    }
    return p;
}

//根据个十百千位排序
void radixSort(vector<int>& vec) {
    int maxbit = maxBit(vec); //最长位数是多少，代表要进行几次排序
    for (int i = 1; i <= maxbit; i++) { //i为多少，代表按第几位数字比较(从右向左)
        vec=countSort(vec, i);
    }
}

//排序结果
vector<int>  countSort(vector<int> vec,int place) {//按指定位置的值进行计数排序
    vector<int> temp(vec); //临时数组，存储place位置的值
    vector<int> ordered(vec); //排好序的数组放进ordered
    int count[10] = {0};
    for (int i = 0; i < vec.size(); i++) {
        temp[i] =(int)(vec[i] / pow(10, place - 1) )% 10; //找到每个元素place位置上的数字存在temp中
    }
    for (int i = 0; i < vec.size(); i++) {
        count[temp[i]] ++; //统计数字出现的频率
    }
    for (int i = 1; i < 10; i++) {
        count[i] = count[i] + count[i - 1]; //此时count中存放着temp中每个数字的索引
    }
    for (int i = vec.size()-1; i >=0; i--) {
        int index = count[temp[i]]-1;
        count[temp[i]]--;
        ordered[index] = vec[i];
    }
    cout << "next:" << endl;
    for (int i = 0; i < vec.size(); i++) {
        cout << ordered[i] << "  ";
    }
   
    return ordered;
}